package leetcode_day._2021._202104._2131;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/26 13:31
 * 在 D 天内送达包裹的能力
 * 船的最大运载能力就是一天把所有的物品都运送完
 * 船的最小运载能力就是所有物品中最重物品的重量
 * 在 [min, max] 区间找到在规定时间内运完物品的最低运载能力
 * 使用二分查找
 * 如果运载能力可以把物品运输完，并且少于规定天数的，那么就再往前找
 * 反之，就要往后找
 * 时间复杂度 O(n * log(m)) m --- 为最大运载能力到最小运载能力的个数
 * 空间复杂度 O(1)
 */
public class _26_1011 {

    public int shipWithinDays(int[] weights, int D) {
        int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
        while (left < right) {
            int mid = (left + right) >> 1;
            int cur = 0, d = 1;
            for (int weight : weights) {
                if (cur + weight > mid) {
                    ++d;
                    cur = 0;
                }
                cur += weight;
            }
            if (d > D) left = mid + 1;
            else {
                right = mid;
            }
        }
        return left;
    }
}
